/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/n-queens-ii
   @Language: C++
   @Datetime: 19-06-20 10:44
   */

class Solution {
	bool isValid(vector<int> &v, int row, int col){
		bool valid=true;
		for(int i=0; valid && i<row; valid=v[i++]!=col);
		for(int i=row; valid && i--; valid=v[i]!=col+i-row);
		for(int i=row; valid && i--; valid=v[i]!=col+row-i);
		return valid;
	}
	int backtrack(vector<int> &v, int row){
		if(row==v.size()) return 1;
		int sum=0;
		for(int col=0; col<v.size(); ++col){
			v[row]=col;
			if(isValid(v,row,col)) sum+=backtrack(v,row+1);
			v[row]=-1;
		}
		return sum;
	}
public:
	int totalNQueens(int n) {
		vector<int> v(n,-1);
		return backtrack(v,0);
	}
};
